#include <iostream>
#include <vector>
#include "mgraph.cpp"

using namespace std;

Status TopoSort(MGraph G, vector<int> &result);

int main(void)
{
	MGraph net(DG);
	Status st;
	vector<int> result;
	int vexs[15][2] = {
						{0,1}, 
						{0,5},
						{0,6},
						{2,0},
						{2,3},
						{3,5},
						{5,4},
						{6,4},
						{6,9},
						{7,6},
						{8,7},
						{9,10},
						{9,11},
						{9,12},
						{11,12}
					};
	for(int i = 0; i <= 12; i++)
	{
		st = net.InsertVex(i);
		if(st != OK)
			cout << "Error in inserting vertex." << endl;
	}
	for(int i = 0; i <= 14; i++)
	{
		st = net.InsertArc(vexs[i][0], vexs[i][1]);
		if(st != OK)
			cout << "Error in inserting arc." << endl;
	}
	// net.InsertArc(4,0);				//build a circuit
	st = TopoSort(net, result);
	if(st == OK)
	{
		cout << "The topological sequence of the net is: ";
		for(vector<int>::iterator i = result.begin(); i != result.end(); i++)
			cout << *i << " ";
		cout << endl;
	}
	return 0;
}

Status TopoSort(MGraph G, vector<int> &result)
{
	if(G.Graphkind == UDG || G.Graphkind == UDN)
		return INFEASIBLE;
	int inDegree[MAX_VERTEX_NUM] = {0}, i, j, vexn = G.vexnum;
	bool visited[MAX_VERTEX_NUM] = {0}, haveZeroInDrgreeVex;
	for(i = 0; i < vexn; i++)
		if(G.arcs[i][i].adj)
		{
			cout << "The graph contains a ring." << endl;
			return ERROR;
		}
	for(i = 0; i < vexn; i++)
		for(j = 0; j < vexn; j++)
			if(G.arcs[j][i].adj)
				inDegree[i]++;
	while(vexn)
	{
		haveZeroInDrgreeVex = false;
		for(i = 0; i < G.vexnum; i++)
			if(inDegree[i] == 0 && !visited[i])
			{
				haveZeroInDrgreeVex = true;
				result.push_back(G.vexs[i]);
				visited[i] = true;
				for(j = 0; j < G.vexnum; j++)
					if(G.arcs[i][j].adj)
						inDegree[j]--;
				vexn--;
			}
		if(haveZeroInDrgreeVex == false && vexn)
		{
			cout << "The graph has a circuit." << endl;
			return ERROR;
		}

	}
	return OK;
}